﻿#include <iostream>

/**
 * 以字母character开头，长度为length的字符有多少个
 */
static int howManyBeginWithCharacter(char character, int length)
{
	if (length == 1)
	{
		return 1;
	}

	int total = 0;
	for (char cur = character + 1; cur <= 'z'; cur++)
	{
		total += howManyBeginWithCharacter(cur, length - 1);
	}

	return total;
}

/**
 * 长度为length的字符串，有多少个?
 */
static int howManyWithLength(int length)
{
	int total = 0;
	for (char cur = 'a'; cur <= 'z'; cur++)
	{
		total += howManyBeginWithCharacter(cur, length);
	}

	return total;
}

static int encode(const char* str)
{
	auto strLen = strlen(str);
	if (strLen == 1)
	{
		return str[0] - 'a' + 1;
	}

	int total = 'z' - 'a' + 1;
	for (int size = 2; size < strLen; size++)
	{
		total += howManyWithLength(size);
	}

	for (char cur = 'a'; cur < str[0]; cur++)
	{
		total += howManyBeginWithCharacter(cur, strLen);
	}

	char prev = str[0];
	int index = 1;
	while (index < strLen)
	{
		for (char cur = prev + 1; cur < str[index]; cur++)
		{
			total += howManyBeginWithCharacter(cur, strLen - index);
		}

		prev = str[index];
		++index;
	}

	return total + 1;
}

//  在数据加密和数据压缩中常需要对特殊的字符串进行编码。给定的字母表A由26个小写英文字母组成，即A =  { a,b,...z }.
//  该字母表产生的长序字符串是指定字符串中字母从左到右出现的次序与字母在字母表中出现的次序相同，且每个字符最多出 现一次。
//  例如，a, b, ab, bc, xyz等字符串是升序字符串。对字母表A产生的所有长度不超过6的升序字符串按照字典排列编码 如下：
//  a(1), b(2), c(3), ..., z(26), ab(27), ac(28), ..., az(51), bc(52), ...
//  对于任意长度不超过16的升序字符串，迅速计算出它在上述字典中的编码。
// 
//  输入描述：
//  第一行是一个正整数N，表示接下来共有N行，在接下来的N行中，每行给出一个字符串。
// 
//  输出描述：
//  输出N行，每行对应于一个字符串编码。
// 
//  示例：
//  输入：
//  3
//  a
//  b
//  ab
// 
// 输出：
//  1
//  2
//  27
// 
// 思路：
//  构建两个函数：
//  1. 求长度为length的字符串一共有多少个: f(length)
//  2. 求以字符c开头，长度为length2的字符串一共有多少个 : g(c, length2)
// 
// 有了这两个函数，就可以求解任意子字符串表示的编码了。
//  比如 "bgl", 可以分解为f(1) + f(2) + g(a, 3) + (b开头，然后第二字符依次是c, d, ..., f, g; 第三字符依次是d, e, ..., k, l)
int main_EncodingByAToZSubStrings()
{
	char input[][18] = {
		"6",
		"a",
		"ab",
		"abc",
		"abcd",
		"uvwx",
		"bc",
	};

	int strCount = 0;
	sscanf_s(input[0], "%d", &strCount);
	for (int i = 0; i < strCount; i++)
	{
		auto curInput = input[i + 1];
		int code = encode(curInput);
		printf("%d\n", code);
	}

	return 0;
}